package cn.chen.数据结构.二叉树.二叉排序树;

public class BinarySortTree {

    BinarySortTreeNode root=null;

    /**
     * 删除该节点为根结点的二叉树中的最小值的节点
     * @param node      以该节点为根结点的二叉树中找到最小值的节点，
     * @return          返回最小节点的值
     */
    public int delMinNode(BinarySortTreeNode node){

        BinarySortTreeNode tRightNode=node;

        // 利用循环找到最小的节点，并且只往左边找，因为二叉排序树的左子树小于根结点
        while(tRightNode.left!=null){

            tRightNode=tRightNode.left;
        }
        // 删除最小节点
        deleteNode(tRightNode.value);

        return tRightNode.value;
    }
    // 删除节点的方法
    public void deleteNode(int value){

        if(root==null)  // root节点为空，说明树为空，没有删除的东西
            return;

        BinarySortTreeNode targeNode = searchTargeNode(root, value);// 要删除的节点
        if(targeNode==null) // 如果要删除的结点为空，说明该树中没有该元素，结束程序
            return; // 结束

        if(root.left==null&&root.right==null) {  // 该树只有一个节点，并且要删除的节点就是该节点
            root = null;
        }

        BinarySortTreeNode parentNode = searchParentNode(root, value);  // 要删除节点的父结点

        // 判断要删除的节点是否是叶子节点
        if(targeNode.left==null&&targeNode.right==null){

            // 父结点为空，并且该节点还是叶子节点的情况就是只有一个节点root，上面已经考虑了
            if(parentNode!=null){   // 父结点不为空

                // 判断targeNode是parentNode的左子节点还是右子节点
                if(parentNode.left!=null&&parentNode.left.value==value)
                    parentNode.left=null;
                if(parentNode.right!=null&&parentNode.right.value==value)
                    parentNode.right=null;
            }

        }
        else if(targeNode.left!=null&&targeNode.right!=null){// 判断要删除的结点是有两个子树的节点

            // 这里不用考虑要删除节点的父结点是否为空，因为这里用不到父结点

            // 将temp(最小节点的值)赋值给要删除的节点
            targeNode.value=delMinNode(targeNode.right);    // 这里传入的参数是targeNode.right，因为是从当前节点的右子树中找到最小的，所以传递是右子节点

        }
        else {  // 要删除的 节点是只有一颗子树的情况

            if(parentNode!=null){   // 父结点不为空,4种情况

                if(parentNode.left!=null){

                    if(targeNode.left!=null)
                        parentNode.left=targeNode.left;
                    else if(targeNode.right!=null)
                        parentNode.left=targeNode.right;
                }
                if(parentNode.right!=null){

                    if(targeNode.left!=null)
                        parentNode.right=targeNode.left;
                    else if(targeNode.right!=null)
                        parentNode.right=targeNode.right;
                }
            }
            else  { // 父结点为空,要删除的节点就是根结点

                if(targeNode.left!=null)
                    root=targeNode.left;
                else if(targeNode.right!=null)
                    root=targeNode.right;
            }

        }
    }
    /**
     * @param node      最开始是root节点
     * @param value     要查询节点的值
     * @return          要删除节点的父结点
     */
    public BinarySortTreeNode searchParentNode(BinarySortTreeNode node,int value){

        if(node==null)
            return null;

        if((node.left!=null&&node.left.value==value)||(node.right!=null&&node.right.value==value))    // 当前节点的左子节点，或右子节点就是要删除的节点
            return node;

        // 当前节点的儿子辈的节点没有是要删除的节点，所以当前节点不是要删除节点的父结点，所以往下遍历
        if(value<node.value&&node.left!=null)
            return searchParentNode(node.left,value);

        if(value>=node.value&&node.right!=null)
            return  searchParentNode(node.right,value);

        return null;
    }
    /**
     * @param node      最开始是根结点root
     * @param value     要找到节点的值
     * @return          要删除的结点
     */
    public BinarySortTreeNode searchTargeNode(BinarySortTreeNode node,int value){

        if(node==null)
            return null;

        if(node.value==value)
            return node;

        if(value<node.value&&node.left!=null)   // 要查找的值比当前节点小，并且当前节点左子树不为空，所以往左递归
            return searchTargeNode(node.left,value);

        if(value>=node.value&&node.right!=null)
            return searchTargeNode(node.right,value);

        return null;    // 没有该节点
    }

    // 插入节点的重载方法
    public void addNode(BinarySortTreeNode node){

        if(node==null)
            return;
        if(root==null) {
            root = node;
            return;
        }
        addNode(root,node);
    }
    /**
     * @param rt    最开始是root（根结点），从root开始遍历，找到node插入的位置
     * @param node  要插入的节点
     */
    private void addNode(BinarySortTreeNode rt, BinarySortTreeNode node){

        if(node.value>=rt.value){  // 要插入的比当前节点的值大或等于，相同值放在右子树

            if(rt.right==null)  // 当前节点的右节点是否为空
                rt.right=node;
            else  // 不为空
                addNode(rt.right,node);
        }
        else{   // 要插入的比当前节点小，往左边放

            if(rt.left==null)
                rt.left=node;
            else
                addNode(rt.left,node);
        }
    }

    // 中序遍历
    public void midOrder(){

        if(root==null){

            System.out.println("二叉排序树为空");
            return;
        }
        midOrder(root);
    }
    // 中序遍历二叉树
    private void midOrder(BinarySortTreeNode node){

        if(node==null)
            return;

        midOrder(node.left);

        System.out.println(node);

        midOrder(node.right);
    }
}
